<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <style>


    </style>

<body>

</body>
<script>
    // var obj1 = (function () {
    //     var inner = '1-1';
    //     return {
    //         inner: '1-2',
    //         say: function () {
    //             console.log(inner);
    //             console.log(this.inner);
    //         }
    //     }
    // })();

    // var obj2 = {
    //     inner: '2-1'
    // }

    // obj1.say();
    // obj2.say = obj1.say;
    // obj2.say();

    // function run() {
    //     var a = 10;
    //     return function () {
    //         a++;
    //         console.log(a);
    //     }
    // }
    // var b = run();
    // b()
    // b()
    // b()
    // var c = run()
    // c()
    // c()
    // c()
    // var a, b;
    // (function () {
    //     console.log(a);
    //     console.log(b);
    //     var a = b = 3;//等同于var a = 3，b = 3;
    //     console.log(a);
    //     console.log(b);
    // })();
    // console.log(a);
    // console.log(b);
    // function A(x) {
    //     this.x = x;
    // }
    // A.prototype.x = 1;

    // function B(x) {
    //     this.x = x;
    // }
    // B.prototype = new A();
    // console.log(B.prototype )
    // var a = new A(2),
    //     b = new B(3);
    //     console.log(a.x)
    //     console.log(b.x)
    // delete b.x;
    // var a = {
    //     b:'b',
    //     c:function(){
    //         console.log(this.b)
    //     }
    // }
    // a.c();
    // var a = {
    //     b:'b',
    //     c:()=>{
    //         console.log(this.b);
    //     }
    // }
    // a.c()
    // var a = {
    //     b:'b',
    //     c:function(){
    //         console.log(this.b);
    //     }
    // }
    // let d = a.c;
    // d();
    // console.log(1);
    // setTimeout(() =>{
    //     console.log(2);
    //     Promise.resolve().then(()=>{
    //         console.log(3)
    //     })
    // })
    // new Promise((resolve,reject) => {
    //     console.log(4)
    //     resolve()
    // }).then(()=>{
    //     console.log(5)
    // })
    // setTimeout(() => {
    //     console.log(6)
    // });
    // console.log(7)
    // 'use strict'
    // var a = 1;
    // var obj = {
    //     a:2,
    //     print:function(){
    //         console.log(this.a)
    //     }
    // }

    // console.log(obj.print());
    // var print = obj.print;
    // print();

    // function removeStr(str) {
    //     if (!str.length) {
    //         return str;
    //     }
    //     let obj = {};
    //     let arr = str.split('');
    //     for(let i = 0;i < arr.length;i++) {
    //         let item = arr[i];
    //         if(typeof obj[item] === 'undefined') {
    //             obj[item] = 1;
    //         }else {
    //             obj[item]++;
    //         }

    //         if(obj[item] === 3) {
    //             arr.splice(i,1);
    //             i--;
    //             obj[item]--;
    //         }
    //         if(i > 1 && obj[arr[i - 2]] === 2 && obj[item] === 2) {
    //             arr.splice(i - 1,1);
    //             i--;
    //             obj[item]--;
    //         }
    //     }
    //     return arr;
    // }
    // console.log(removeStr("aabbcccdd"))


    // 获取当前日期（输出格式：年-月-日 星期 时：分：秒）；
    // var weekday = ['星期一', '星期二', '星期三', '星期四', '星期五', '星期六', '星期日']

    // function myDate() {
    //     var d = new Date();
    //     var year = d.getFullYear();
    //     var month = d.getMonth() + 1;
    //     var day = d.getDate();
    //     var week = d.getDay();
    //     var hour = d.getHours();
    //     var min = d.getMinutes();
    //     var sec = d.getSeconds();
    //     var w = weekday[week - 1];
    //     var str = `${year}年${month}月${day}日 ${w} ${hour}：${min}：${sec}`
    //     return str;
    // }
    // console.log(myDate())

    // function quickSort(arr) {
    //     if (arr.length <= 1) {
    //         return arr;
    //     }
    //     let midIndex = Math.floor(arr.length / 2);
    //     let midNum = arr.splice(midIndex, 1)[0];
    //     let left = [];
    //     let right = [];
    //     for (let i = 0; i < arr.length; i++) {
    //         if (arr[i] < midNum) {
    //             left.push(arr[i]);
    //         } else {
    //             right.push(arr[i]);
    //         }
    //     }
    //     return quickSort(left).concat([midNum], quickSort(right));
    // }
    // var arr = [1, 23, 12, 7, 3, 28, 2, 14];
    // console.log(quickSort(arr));
    // 实现从一个无序数组，选取n个数，使其和为m的算法
    // function sumM(arr, n, m) {
    //     let vis = new Array(arr.length).fill(false);
    //     let res = []
    //     var dfs = function (a, count, sum) {
    //         if (sum >= m && count < n) {
    //             return;
    //         }
    //         if (count >= n && sum < m) {
    //             return;
    //         }
    //         if (sum === m && count === n) {
    //             res = a.slice(0);
    //             console.log(res);
    //             return;
    //         }

    //         for (let i = 0; i < arr.length; i++) {
    //             if (!vis[i]) {
    //                 vis[i] = true;
    //                 a.push(arr[i]);
    //                 count++;
    //                 sum += arr[i];
    //                 dfs(a, count, sum);
    //                 vis[i] = false;
    //                 a.pop();
    //                 count--;
    //                 sum -= arr[i]
    //             }
    //         }
    //     }
    //     dfs([],0,0);
    //     return res;
    // }
    // var arr = [1, 23, 12, 7, 3, 28, 2, 14];
    // console.log(sumM(arr, 3, 20));
    // var dic = ["I","have","a","book","good"];
    //  function isDic(s) {
    //     let arr = s.split(" ");
    //     console.log(arr);
    //     for(let i = 0; i < arr.length;i++) {
    //         if(!dic.includes(arr[i])) {
    //             return false;
    //         }
    //     }
    //     return true;
    //  }
    //  var s = "good book";
    //  console.log(isDic(s));

    // 走台阶
    // function footStep(n) {
    //     let dp = new Array(n);
    //     dp[0] = 1;
    //     dp[1] = 2;
    //     for(let i = 2;i < n;i++) {
    //         dp[i] = dp[i - 1] + dp[i - 2];
    //     }
    //     return dp[n - 1];
    // }
    // console.log(footStep(40000))
    // var arr = [32, 3, 1, 5, 1, 30, 76, 2, 10, 29]
    // n = 31;

    // function find(arr, n) {
    //     let res = [];
    //     arr.sort((a, b) => a - b);
    //     let left = 0,
    //         right = arr.length - 1;
    //     while (left < right) {
    //         if (arr[left] + arr[right] > n) {
    //             right--
    //         } else if (arr[left] + arr[right] < n) {
    //             left++;
    //         } else {
    //             res.push([arr[left] , arr[right]])
    //             right--;
    //             left++;
    //         }
    //     }
    //     return res;

    // }

    // console.log(find(arr, n));

    // var minWindow = function (s, t) {
    //     let need = {},
    //         window = {};
    //     for (let key of t) {
    //         if (!need[key]) {
    //             need[key] = 1;
    //         } else {
    //             need[key]++;
    //         }
    //     }
    //     let left = 0,
    //         right = 0;
    //     let valid = 0,
    //         len = Object.keys(need).length;
    //     let minLen = s.length + 1,
    //         minStr = "";
    //     while (right < s.length) {
    //         const temp = s[right];
    //         right++;
    //         if (!window[temp]) {
    //             window[temp] = 1;
    //         } else {
    //             window[temp]++;
    //         }
    //         if (need[temp] && window[temp] === need[temp]) {
    //             valid++;
    //         }
    //         while (valid === len) {
    //             if (right - left < minLen) {
    //                 minLen = right - left;
    //                 minStr = s.slice(left, right);
    //             }
    //             let c = s[left];
    //             left++;
    //             window[c]--;
    //             if (need[c] && window[c] < need[c]) {
    //                 valid--;
    //             }
    //         }


    //     }
    //     return minStr;
    // };

    // var s = "ADOBECODEBANC",
    //     t = "ABC"
    // console.log(minWindow(s, t));

    // var maxEnvelopes = function (envelopes) {
    //     if(envelopes.length === 1) {
    //         return 1;
    //     }
    //     envelopes.sort((a,b)=>{
    //         if(a[0] !== b[0]) {
    //             return a[0] - b[0];
    //         }else {
    //             return b[1] - a[1];
    //         }
    //     })
    //     let LISArr = [];
    //     for(let [key, value] of envelopes) {
    //         LISArr.push(value);
    //     }
    //     return LIS(LISArr);
    // };
    // function LIS(arr) {
    //     let dp = new Array(arr.length).fill(1);
    //     let maxAns = 0;
    //     for(let i = 1;i < arr.length;i++) {
    //         for(let j = 0;j < i;j++) {
    //             if(arr[i] > arr[j]) {
    //                 dp[i] = Math.max(dp[i],dp[j] + 1);
    //             }
    //             if(maxAns < dp[i]) {
    //                 maxAns = dp[i];
    //             }
    //         }
    //     }
    //     return maxAns
    // }
    // var envelopes = [[4,5],[4,6],[6,7],[2,3],[1,1]]
    // console.log(maxEnvelopes(envelopes));
    // var permute = function (nums) {
    //     let ans = []
    //     if (nums.length === 1) {
    //         return ans.push(nums.slice());
    //     }
    //     const dfs = function (start) {
    //         if (start >= nums.length) {
    //             ans.push(nums.slice());
    //             return;
    //         }
    //         for (let i = start; i < nums.length; i++) {
    //             let t = nums[i];
    //             nums[i] = nums[start];
    //             nums[start] = t;
    //             dfs(start + 1);
    //             t = nums[i];
    //             nums[i] = nums[start];
    //             nums[start] = t;

    //         }
    //     }
    //     dfs(0)
    //     return ans;
    // };
    // console.log(permute([1]));

    // function sliceArray(arr, count) {
    //     // 平均值向上取整
    //     let average = Math.ceil(arr.reduce((acc, v) => acc + v, 0) / count)
    //     // 由大到小排列
    //     arr.sort((n1, n2) => n2 - n1)
    //     const getArr = () => {
    //         let sum = 0,
    //             newArr = [] // 存相应数据
    //         arr.map((v, i) => {
    //             if (sum + v <= average) {
    //                 sum += v
    //                 newArr.push(v)
    //                 arr.splice(i, 1)
    //             }
    //         })
    //         return newArr;
    //     }

    //     let backArr = new Array(count).fill(0)
    //     backArr.forEach((x, i) => {
    //         backArr[i] = i === backArr.length - 1 ? arr : getArr()
    //     })
    //     return backArr
    // }
    // console.log(sliceArray([1, 2, 3, 4, 5], 3));

    // 字符串去重
    // 给定一个长度小于 50 且包含字母，数字和特殊字符的字符串，提取其中的数字和字母并且把数字去重，
    // 最后输出时数字在前面，字母放在后面，且维持在其原字符串中的位置。

    // function f(str) {
    //     let set = new Set()
    //     let number = []
    //     let string = []
    //     for(let i = 0;i < str.length;i++) {
    //         if(str[i] >= '0' && str[i] <= '9') {
    //             if(!set.has(str[i])) {
    //                 number.push(str[i])
    //             }
    //         } else if ((str[i] >='A' && str[i] <= 'Z')|| (str[i] >= 'a' && str[i] <= 'z')) {
    //             string.push(str[i])
    //         }
    //     }
    //     console.log(number);
    //     console.log(string);
    //     return  number.join("") + string.join("")
    // }

    // console.log(f('14-4a635a*&Kco'));

// 归并排序
    function mergeSort(arr) {
        let len = arr.length;
        if (len < 2) return arr;
        let mid = Math.floor(len / 2);
        let left = arr.slice(0, mid);
        let right = arr.slice(mid);

        return merge(mergeSort(left), mergeSort(right));
    }

    function merge(left, right) {
        let result = [];
        let i = 0,
            j = 0;
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result.push(left[i])
                i++
            } else {
                result.push(right[j])
                j++
            }
        }
        while (i < left.length) {
            result.push(left[i])
            i++
        }
        while (j < right.length) {
            result.push(right[j])
            j++
        }

        return result;
    }


    // 冒泡排序
    function bubbleSort(arr) {
        for (let i = 0; i < arr.length; i++) {
            for (let j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    [arr[i], arr[j]] = [arr[j], arr[i]]
                }
            }
        }
        return arr
    }

    // 选择排序
    function selectSort(arr) {
        for (let i = 0; i < arr.length; i++) {
            let minIndex = i;
            for (let j = i + 1; j < arr.length; j++) {
                if (arr[minIndex] > arr[j]) {
                    minIndex = j
                }
            }
            if (minIndex != i) {
                [arr[minIndex], arr[i]] = [arr[i], arr[minIndex]]
            }
        }
        return arr
    }

    // 插入排序
    function insertSort(arr) {
        for (let i = 0; i < arr.length; i++) {
            let j = i - 1;
            let current = arr[i]
            while (j >= 0 && arr[j] > current) {
                arr[j + 1] = arr[j]
                j--;
            }
            arr[j + 1] = current
        }
        return arr
    }

    // 希尔排序
    function shellSort(arr) {
        for (let d = parseInt(arr.length / 2); d > 0; d = parseInt(d / 2)) {
            for (let i = d; i < arr.length; i++) {
                for (let j = i - d; j >= 0; j -= d) {
                    if (arr[j] > arr[j + d]) {
                        let temp = arr[j];
                        arr[j] = arr[j + d];
                        arr[j + d] = temp;
                    }
                }
            }
        }
        return arr
    }

    // 快速排序
    function quickSort(arr) {
        if(arr.length < 2) {
            return arr
        }
    //    选取基值
        let mid = parseInt(arr.length / 2)
        let midVal = arr.splice(mid,1)[0]
        let left = []
        let right = []
        for(let i = 0;i < arr.length;i++) {
            if(arr[i] <= midVal) {
                left.push(arr[i])
            } else {
                right.push(arr[i])
            }
        }
        return quickSort(left).concat([midVal],quickSort(right))
    }

    var arr = [3, 5, 7, 1, 4, 56, 12, 78, 25, 0, 9, 8, 42, 37];
    // var res = mergeSort(arr);
    // console.log(arr, res)
    // console.log(bubbleSort(arr));
    // console.log(selectSort(arr));
    // console.log(insertSort(arr));
    // console.log(shellSort(arr));
    console.log(quickSort(arr));
</script>
</body>

</html>